<?php
class TestController extends Controller {
	
	function index (){
		
	}
	
	/**
	 * Bài toán sắp xếp
	 * Enter description here ...
	 */
	var $listSort = array();
	function sort(){
	
		if (!empty($this->request->data)){
			if (is_numeric($this->data['sort']['arraysort'])){
				$number = (int)($this->data['sort']['arraysort']);
			}
			
			if (isset($number)){
				for ($i = 0; $i < $number; $i++){
					$randomNum = mt_rand(1, 10000);
					$this->listSort[] = $randomNum;
					
				}
				if (isset($this->listSort) && !empty($this->listSort)){
					$arrBegin = $this->listSort;
					
					$fpbegin = fopen("D:\begin.txt", "w+") or exit("khong tim thay file");
					foreach ($arrBegin as $arrBegin){
							fwrite($fpbegin, $arrBegin);
							fwrite($fpbegin, ",");
					}
					fclose($fpbegin);
					
					if (!empty($this->data['quicksort'])){
						$timeStartRun = microtime(true);
						$this->__quicksort(0, $number-1);
						$timeRun = microtime(true) - $timeStartRun;
					}
					
					if (!empty($this->data['bublesort'])){
						$timeStartRun = microtime(true);
						$this->__bublesort($number-1);
						$timeRun = microtime(true) - $timeStartRun;
					}
				
					$arrResult = $this->listSort;
					$fpresult = fopen("d:\end.txt", "w+")or exit("khong tim thay file");
					foreach ($arrResult as $arrResult){
						fwrite($fpresult, $arrResult);
						fwrite($fpresult, ",");
					}
					fclose($fpresult);
					
					$this->set(compact('timeRun'));
				}
			}
		}
		$this->set('title_for_content', 'Bài toán sắp xếp');
	}

	function __quicksort($left, $right){		
		$i = $left;
		$j = $right;
		if ($i >= $j){
			return;
		}
		$tg = $this->listSort[(int)(($left + $right)/2)];
		while ($i <= $j){
			while ($this->listSort[$i] < $tg){
				$i++;
			}
			while ($this->listSort[$j] > $tg){
				$j--;
			}
			if ($i <= $j){
				$temp = $this->listSort[$i];
				$this->listSort[$i] = $this->listSort[$j];
				$this->listSort[$j] = $temp;
				$i++; $j--;
			}
		}		
		$this->__quicksort($left, $j);
		$this->__quicksort($i, $right);
	}
	
	
	/**
	 *  bai toan bublesort
	 * Enter description here ...
	 * @var unknown_type
	 */
	function __bublesort($number){
		$i = $number;
		while ($i >= 0) {
			for ($j = 0; $j < $i; $j ++){
				if ($this->listSort[$j] > $this->listSort[$j+1]){
					$temp = $this->listSort[$j];
					$this->listSort[$j] = $this->listSort[$j+1];
					$this->listSort[$j+1] = $temp;
				}
			}
			$i--;
		}
	}
	
	
	
	
	
	
		
	/**
	 * bài toán con mã đi tuần
	 * Enter description here ...
	 * @var unknown_type
	 */
	var $a = array(-2,-1,1,2,2,1,-1,-2);
	var	$b = array(1,2,2,1,-1,-2,-2,-1);
	var $result =  array();
	var $time = null;
	var $size = null;
	var $timeRun = 0;
	var $__found = false;
	
	function madituan(){
		if (!empty($this->request->data)){
//			debug($this->data);die;
			$size = $this->data['ma_di_tuan']['kich_thuoc'];
			$time = $this->data['ma_di_tuan']['time'];
			$this->time = $time;
			$this->size = $size;
			$toaDoX = $this->data['ma_di_tuan']['toa_do_x'];
			$toaDoY = $this->data['ma_di_tuan']['toa_do_y'];
			// khoi tao ban co
			for ($i = -1; $i <= ($size + 2); $i++){
				for ($j = -1; $j <= ($size + 2); $j++){					
					$this->result[$i][$j] = -1;					 
				}
			}
			
			for ($i = 1; $i <= $size; $i++){
				for ($j = 1; $j <= $size; $j++){					
					$this->result[$i][$j] = 0;					 
				}
			}
			$this->result[$toaDoX][$toaDoY] = 1;

			$this->timeRun = microtime(true);
			$timeStartRun = microtime(true);		
			$this->__nuocdi(1, $toaDoX, $toaDoY);
			$timeRun = microtime(true) - $timeStartRun;
			if (!$this->__found){
				if ($timeRun > $this->time){
					$timeOut = 2;
				}else{
					$timeOut = 1;
				}
			}else {
				$result = $this->result;
				$timeRunInfo = $timeRun;
			}
			
			$this->set(compact('result', 'timeRunInfo', 'timeOut', 'size'));
		}
		$this->set('title_for_content', 'Mã đi tuần');
		
	}
	

	function __nuocdi($n, $x, $y){
		if (microtime(true) - $this->timeRun >= $this->time){
				return ;
		}
		for ($k = 0 ; $k < 8; $k++){
			$xNew = $x + $this->a[$k];
			$yNew = $y + $this->b[$k];
			if (($this->result[$xNew][$yNew]) == 0 ){
					$this->result[$xNew][$yNew] = $n+1 ;
					if ($n+1 >= ($this->size*$this->size) ){
						$this->__found = true;
						return ;
					}
					$this->__nuocdi($n+1, $xNew, $yNew);	
																
					if ($this->__found == true){
						return ;
					}
					// Tra lai trang thai cu cho mang 
					$this->result[$xNew][$yNew] = 0;
			}
		}
	}
	

}